package com.caochenlei.graph;

public class DepthFirstSearch {
    private boolean[] marked;                   //索引代表顶点，值表示当前顶点是否已经被搜索
    private int count;                          //记录有多少个顶点与顶点s相通

    public DepthFirstSearch(Graph G, int s) {   //构造深度优先搜索对象
        this.marked = new boolean[G.size()];    //初始化marked数组
        this.count = 0;                         //初始化跟顶点s相通的顶点的数量
        dfs(G, s);                              //使用深度优先搜索找出G图中顶点s的所有相邻顶点
    }

    private void dfs(Graph G, int v) {          //使用深度优先搜索找出G图中顶点v的所有相通顶点
        marked[v] = true;                       //把顶点v标识为已搜索
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                dfs(G, w);                      //如果没有被搜索过，则递归调用dfs方法进行深度搜索
            }
        }
        count++;
    }

    //判断w顶点与顶点s是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }
}
